home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus Leser 19 / Amiga Plus Leser CD 19.iso / Online / AmigaTalk / examples / TuringMachineSim.st < prev   
Text File  |  2002-01-30  |  3KB  |  133 lines
  1. "
  2.    Turing machine simulator contributed by Jan Gray,
  3.    the University of Waterloo
  4. "
  5.  
  6. Class Main
  7. [
  8.   main | tm |
  9.     tm <- TuringMachine new initialize.
  10.  
  11.     tm delta state: 0 input: $# nextState: 1 output: $L.
  12.     tm delta state: 1 input: $I nextState: 1 output: $i.
  13.     tm delta state: 1 input: $i nextState: 1 output: $L.
  14.     tm delta state: 1 input: $# nextState: 2 output: $R.
  15.     tm delta state: 2 input: $i nextState: 2 output: $R.
  16.     tm delta state: 2 input: $# nextState: 'halt' output: $#.
  17.     tm tape: 'IIIIII'.
  18.     tm delta print.
  19.     tm run
  20. ]
  21.  
  22. Class TuringMachine
  23. !  tape      "Infinite tape"
  24.    state     "Current state, TM continues if state is a number"
  25.    delta     "A TransitionTable, which for each (state, input)
  26.               gives (next state, output)"
  27.    tapeMoves "A Dictionary which maps L and R into [tape left]
  28.               and [tape right]"
  29. !
  30. [
  31.   initialize
  32.     tapeMoves <- Dictionary new.
  33.     tapeMoves at: $L put: [tape left].
  34.     tapeMoves at: $R put: [tape right].
  35.  
  36.     delta <- TransitionTable new.
  37.  
  38.     self tape: ''.
  39.     self state: 0
  40. |
  41.   tape: aString
  42.     tape <- Tape new with: aString
  43. |
  44.   state: aState
  45.     state <- aState
  46. |
  47.   delta
  48.     ^ delta
  49. |
  50.   step | next |
  51.     next  <- delta atState: state input: tape read.
  52.     state <- next state.
  53.  
  54.     (state isKindOf: Number)
  55.        ifTrue: [(tapeMoves includesKey: next symbol)
  56.                  ifTrue:   [(tapeMoves at: next symbol) value]
  57.                  ifFalse: [tape write: next symbol]
  58.                ]
  59. |
  60.   run
  61.     state <- 0.
  62.     self print.
  63.     [state isKindOf: Number] whileTrue: [self step print]
  64. |
  65.   printString
  66.     ^ 'State ', state printString, ', Tape ', tape printString
  67. ]
  68.  
  69. Class Pair :Magnitude ! state symbol !
  70. [
  71.   state: aState symbol: aSymbol
  72.     state  <- aState.
  73.     symbol <- aSymbol
  74. |
  75.   state
  76.     ^ state
  77. |
  78.   symbol
  79.     ^ symbol
  80. |
  81.   < aPair
  82.     ^ state < aPair state or: [state = aPair state 
  83.                                 and: [symbol < aPair symbol]
  84.                               ]
  85. |
  86.   printString
  87.     ^ state printString, '   ', symbol printString
  88. ]
  89.  
  90. Class TransitionTable :Dictionary
  91. [
  92.   state: aState input: in nextState: nextState output: out
  93.    self at: (Pair new state: aState symbol: in)
  94.        put: (Pair new state: nextState symbol: out).
  95.    ^ nil
  96. |
  97.   atState: aState input: in
  98.     ^ self at: (Pair new state: aState symbol: in)
  99.          ifAbsent: [^ Pair new state: 'hung' symbol: nil].
  100. |
  101.   print
  102.     'State   Read   Next   Write' print.
  103.     self binaryDo: [:x :y | (x printString , '   ', y printString) print]
  104. ]
  105.  
  106. Class Tape :Object ! tape position !
  107. [
  108.   with: aString
  109.     tape     <- '#', aString, '#'.
  110.     position <- tape size
  111. |
  112.   read
  113.     ^ tape at: position
  114. |
  115.   write: aChar
  116.     tape at: position put: aChar.
  117. |
  118.   left
  119.     (position > 1)
  120.        ifTrue: [position <- position - 1]
  121. |
  122.   right
  123.     (position = tape size)
  124.        ifTrue: [tape <- tape, '#'].
  125.  
  126.     position <- position + 1
  127. |
  128.   printString
  129.     ^ (tape copyFrom: 1 to: position - 1), '{',
  130.        ((tape at: position) asString), '}',
  131.        (tape copyFrom: position + 1 to: tape size)
  132. ]
  133.